package com.itheima.algorithm.stack;

import java.util.Calendar;
import java.util.LinkedList;

/**
 * @author: TylerZhong
 * @description:
 */
public class E03InfixToSuffix {
    public static void test() {
        int a = 10;
        int b = 20;
        int c = 5;
        int d = (a+b) * c; // ab+c*
    }

    public static String infixToSuffix(String exp){
        LinkedList<Character> stack = new LinkedList<>();
        StringBuilder sb = new StringBuilder(exp.length());
        for (int i = 0; i < exp.length(); i++) {
            char c = exp.charAt(i);
            switch (c) {
                case '+','-','*','/' -> {
                    if (stack.isEmpty() || priority(c) > priority(stack.peek())) {
                        stack.push(c);
                    } else {
                        while (!stack.isEmpty() && priority(stack.peek()) >= priority(c)) {
                            sb.append(stack.pop());
                        }
                        stack.push(c);
                    }
                }
                case '(' -> stack.push(c);
                case ')' -> {
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        sb.append(stack.pop());
                    }
                    stack.pop();
                }
                default -> sb.append(c);
            }
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }

    public static int priority(char c){
        return switch (c) {
            case '(' -> 0;
            case '+', '-' -> 1;
            case '*', '/' -> 2;
            default -> throw new IllegalArgumentException("不合法运算符：" + c);
        };
    }

    /**
     * a+b          ab+
     * a+b-c        ab+c-
     * a*b+c        ab*c+
     * a+b*c-d      abc*+
     * a+b*c-d      abc*+d-
     * (a+b)*c      ab+c*
     * (a+b*c-d)*e  abc*+d-e*
     * a*(b+c)      abc+*
     *
     * 1. 遇到非运算符   直接拼串
     * 2. 遇到 + - * /
     *      - 它的优先级比较栈顶运算符高，入栈
     *      - 否则把栈里优先级 >= 它 的都出栈，它再入栈
     * 3. 遍历完成，栈里剩余运算符依次出栈
     * @param args
     */
    public static void main(String[] args) {
//        test();
        System.out.println(infixToSuffix("a+b"));
        System.out.println(infixToSuffix("a+b-c"));
        System.out.println(infixToSuffix("a+b*c"));
        System.out.println(infixToSuffix("a*b-c"));

        System.out.println(infixToSuffix("(a+b)*c"));
        System.out.println(infixToSuffix("(a+b*c-d)*e"));
        System.out.println(infixToSuffix("a*(b+c)"));
    }
}
